package alogrithm.solution;

import java.util.Stack;

import alogrithm.structure.TreeNode;

/*
 * transformer a binary tree to double linkedList
 * rightChild delegate post,while leftChild delegates pre.
 */
public class P1 {
	//Without recursive
	public static TreeNode transformerWithoutRecursive(TreeNode node)
	{
		Stack<TreeNode> s=new Stack<TreeNode>();
		TreeNode pre=null,current=node,head=null;
		if(current==null)return null;
		while((!s.isEmpty())||current!=null)
		{
			while(current!=null)
			{
				s.push(current);
				current=current.getLeftChild();		
			}
			current=s.pop();
			current.setLeftChild(pre);
			if(pre!=null)
			{
				pre.setRightChild(current);
				
			}
			else
			{
				head=current;
			}
			pre=current;
			current=current.getRightChild();
		}
		return head;
	}
	
	//Using recursive
	public static TreeNode transformerUsingRecursive(TreeNode node)
	{
		if(node==null)return null;
		TreeNode post=transformerUsingRecursive(node.getRightChild());
		node.setRightChild(post);
		TreeNode pre=transformerUsingRecursive(node.getLeftChild());
		if(pre==null)return node;
		TreeNode head=pre;
		while(pre.getRightChild()!=null)pre=pre.getRightChild();
		pre.setRightChild(node);
		node.setLeftChild(pre);
		return head;
	}
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode n1=new TreeNode(4);
		TreeNode n2=new TreeNode(8);
		TreeNode n3=new TreeNode(12);
		TreeNode n4=new TreeNode(16);
		TreeNode n5=new TreeNode(6,n1,n2);
		TreeNode n6=new TreeNode(14,n3,n4);
		TreeNode n7=new TreeNode(10,n5,n6);
		TreeNode.middleOrderUsingRecursive(n7);
		System.out.println();
		TreeNode.middleOrderWithoutRecursive(n7);
		System.out.println();
		//TreeNode head=transformerWithoutRecursive(n7);
		TreeNode head=transformerUsingRecursive(n7);
		while(head!=null)
		{
			System.out.print(head+"\t");
			head=head.getRightChild();
		}

	}

}
